#ifndef __RABINFP__H
#define __RABINFP__H
#include <inttypes.h>
#include <unistd.h>
#include <memory.h>

#include "ptypes.h"

namespace RabinFP {

template<uint64_t RABIN_BASE, int WINDOW_SIZE, int WINNOWING_SIZE, Fingerprint QUALIFICATION_MASK>
class RabinFingerprint {
public:

  RabinFingerprint() :
    m_accum(0L), m_buffer_length(0), m_buffer_position(0),
    m_ring_pointer(0), m_min_index(0) {

    coefficients = new uint64_t[WINDOW_SIZE];
    if (NULL == coefficients)
      throw "No Memory";
    coefficients[WINDOW_SIZE - 1] = 1;
    for(int i = WINDOW_SIZE - 2; i >= 0; i--) {
      coefficients[i] = coefficients[i + 1] * RABIN_BASE;
    }

    m_hashes = new uint64_t[WINNOWING_SIZE];
    if (NULL == m_hashes)
      throw "No Memory";
    memset(m_hashes, '\0', sizeof(Fingerprint) * WINNOWING_SIZE);
  }

  ~RabinFingerprint() {
    delete[] coefficients;
    delete[] m_hashes;
  }

  void Reset(unsigned char *parray, int length) {
    // circular buffer implementing window of size w
    for (int i=0; i < WINNOWING_SIZE; ++i) 
      m_hashes[i] = 0xFFFFFFFFFFFFFFFFLL;
          
    m_ring_pointer = 0;
        
    m_buffer_position = -1;  // not calculated yet
    m_buffer = parray; // ephemeral buffer pointer
    m_buffer_length = length;
    m_accum = 0;
  }     

  inline Fingerprint FullFingerprint(int pos)  __attribute__((always_inline)) {
    int length = WINDOW_SIZE;

    if(m_buffer_length - pos < length) {
      length = m_buffer_length - pos;
    }
    
    Fingerprint f = 0;
    for(int i = 0; i < length; i++) {
      f += coefficients[i] * m_buffer[i + pos];
    }
    return f;
  }

  inline Fingerprint NextQualifiedFingerprint(int &pos)  __attribute__((always_inline)) {
    for(;;) {
      Fingerprint f = NextFingerprint(pos);
      if(-1 == pos) {
        return 0; // no more data
      }
      if(0 == (QUALIFICATION_MASK & f)) {
        return f;
      }
    }
    return 0;
  }

  inline Fingerprint NextWinnowedFingerprint(int &pos) __attribute__((always_inline)) {

    for(;;) {
      Fingerprint f = NextFingerprint(pos);
      if(0 == pos) {
        // fill the window
        int i;
        m_hashes[0] = f;
        m_ring_pointer = 0;
        m_min_index = 0;
        for(i = 1; i < WINNOWING_SIZE; i++) {
          f = NextFingerprint(pos);
          if(pos < 0) {
            // fake fill, cam't be a minimum
            for(; i < WINNOWING_SIZE; i++) {
              m_hashes[i] = 0xFFFFFFFFFFFFFFFFLL;
            }
            break;
          }
          m_hashes[i] = f;

        }
        // this finds minimum in the just-filled window
        for(i = 1; i < WINNOWING_SIZE; i++) {
          if(m_hashes[i] == 0xFFFFFFFFFFFFFFFFLL)
            break;
          if(m_hashes[i] < m_hashes[m_min_index])
            m_min_index = i;
        }
        m_ring_pointer=-1; // next one should be 0, too
        pos = m_min_index;
        return m_hashes[m_min_index]; // first call
      }

      if(-1 == pos) {
        return 0; // no more data
      }

      m_ring_pointer = (m_ring_pointer + 1) % WINNOWING_SIZE; // shift the window by one
      m_hashes[m_ring_pointer] = f; // and add the hash

     // regular work
      if(m_min_index == m_ring_pointer) {
        // The previous minimum is no longer in this
        // window. Scan h leftward starting from r
        // for the rightmost minimal hash. Note min
        // starts with the index of the rightmost
        // hash.
        for(int i = (m_ring_pointer + WINNOWING_SIZE - 1) % WINNOWING_SIZE;
            i != m_ring_pointer; i = (i - 1 + WINNOWING_SIZE) % WINNOWING_SIZE ) {

          if (m_hashes[i] < m_hashes[m_min_index])
           m_min_index = i;
        }

        int shift = ( (-m_min_index + m_ring_pointer + WINNOWING_SIZE) % WINNOWING_SIZE );
        pos = m_buffer_position -1  - shift;

        return m_hashes[m_min_index];

      } else {
        // Otherwise, the previous minimum is still in
        // this window. Compare against the new value
        // and update min if necessary.
        if(f < m_hashes[m_min_index]) {
          m_min_index = m_ring_pointer;
          pos = m_buffer_position - 1;
          return f;
        }
      }
    }
  }

private:

  uint64_t *coefficients;
  Fingerprint *m_hashes;

  Fingerprint m_accum;
  int m_buffer_length;
  int m_buffer_position;
  int m_ring_pointer;
  int m_min_index;

  unsigned char *m_buffer;

  inline Fingerprint FirstFingerprint(int &pos)  __attribute__((always_inline)) {
    pos = 0;
    m_accum = FullFingerprint(0);
    m_buffer_position=1;
    return  m_accum;
  }

  inline Fingerprint NextFingerprint(int &pos)  __attribute__((always_inline)) {
    if(-1 == m_buffer_position) {
      return FirstFingerprint(pos);
    } else {
      if(m_buffer_position >= m_buffer_length - WINDOW_SIZE) {
        pos = - 1;
        return 0;
      }

      Fingerprint ret=0;
      m_accum -= coefficients[0]*m_buffer[m_buffer_position - 1];

      pos = m_buffer_position;
      m_accum = m_accum * coefficients[WINDOW_SIZE - 2] + m_buffer[m_buffer_position + WINDOW_SIZE - 1];
      m_buffer_position++;
      return  m_accum;
    }
  }

};

}
#endif
